package crazy.tree;

public class TwoLinkBinTree<T>
{
	public static class TreeNode
	{
		Object data;
		TreeNode left;
		TreeNode right;
		
		public TreeNode()
		{}
		
		public TreeNode(Object data)
		{
			this.data = data;
		}
		
		public TreeNode(Object data, TreeNode left, TreeNode right)
		{
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}
	
	private TreeNode root;
	
	public TwoLinkBinTree()
	{
		this.root = new TreeNode();
	}
	
	public TwoLinkBinTree(T data)
	{
		this.root = new TreeNode(data);
	}
	
	public TreeNode addNode(TreeNode parent, T data, boolean isLeft)
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}
		
		if (isLeft && parent.left != null)
		{
			throw new RuntimeException("left node exists");
		}
		
		if (!isLeft && parent.right != null)
		{
			throw new RuntimeException("right node exists");
		}
		
		TreeNode newNode = new TreeNode(data);
		if (isLeft)
		{
			parent.left = newNode;
		}
		else
		{
			parent.right = newNode;
		}
		
		return newNode;
	}
	
	public boolean empty()
	{
		return root.data == null;
	}
	
	public TreeNode root()
	{
		if (empty())
		{
			throw new RuntimeException("tree is null");
		}
		return root;
	}
	
	public T parent(TreeNode node)
	{
		return null;
	}
	
	public T leftChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}
		return parent.left == null? null:(T) parent.left.data;
	}
	
	public T rightChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}
		
		return parent.right == null? null: (T)parent.right.data;
	}
	
	public int deep()
	{
		return deep(root);
	}
	
	public int deep(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		
		if (node.left == null && node.right == null)
		{
			return 1;
		}
		else
		{
			int leftDeep = deep(node.left);
			int rightDeep = deep(node.right);
			int max = leftDeep > rightDeep ? leftDeep : rightDeep;
			return max+1;
		}
	}
}
